package offer;

import treeTraversal.PreorderTraversal;

import java.util.ArrayList;
import java.util.List;

/**
 * @Auther: wangliuyang
 * @Date: 2021/4/25 21:44
 * @Description: 剑指 Offer 26. 树的子结构(不是子树),以下为判断子树代码
 */
public class Offer_26 {
    /**
     * Desc:判断子结构
     * @param A
     * @param B
     * @return {@link boolean}
     * @author wangliuyang
     * @date
     */
        public boolean isSubStructureOffer(TreeNode A, TreeNode B) {
            return (A != null && B != null) && (recur(A, B) || isSubStructureOffer(A.left, B) || isSubStructureOffer(A.right, B));
        }
        boolean recur(TreeNode A, TreeNode B) {
            if(B == null) {
                return true;
            }
            if(A == null || A.val != B.val) {
                return false;
            }
            return recur(A.left, B.left) && recur(A.right, B.right);
        }






    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        preorderTraversal(A,sb1);
        preorderTraversal(B,sb2);
        String s1 = sb1.toString();
        String s2 = sb2.toString();
        return s1.contains(s2);
    }
    public StringBuilder preorderTraversal(TreeNode root ,StringBuilder sb) {
        if (root == null) {
            sb.append("#");
            return sb;
        }
        sb.append(root.val);
        preorderTraversal(root.left,sb);
        preorderTraversal(root.right,sb);
        return sb;
    }


    /**
     * Desc:方法二，通过比较树是否相等来判断是否为子树
     * @param A
     * @param B
     * @return {@link boolean}
     * @author wangliuyang
     * @date
     */
    public boolean isSubStructure1(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        return isSameTree(A,B) || isSubStructure1(A.left,B) || isSubStructure1(A.right,B);
    }
    public boolean isSameTree(TreeNode node1 ,TreeNode node2) {
        if (node1 == null && node2  == null) {
            return true;
        }
        if (node1 == null ){
            return false;
        }
        if (node2 == null) {
            return false;
        }
        if (node1.val != node2.val) {
            return false;
        }
        return isSameTree(node1.left, node2.left) && isSameTree(node1.right,node2.right);
    }
}
